package dotsandboxs;

import java.util.Stack;
import java.util.Vector;

public class ModifiedAI {
    /**
     * 棋盘的行
     */
    final int ROWS = 6;
    /**
     * 棋盘的列
     */
    final int COLS = 6;
    /**
     * 自由度为2
     */
    final int DOFISTWO = 2;
    /**
     * 存放可下边 、 长度为1的短链、长度为2的短链的三个向量
     */
    Vector<Vector<Integer>> move = new Vector<>();
    /**
     * 存放长度为3 - 8长链的向量
     */
    Vector<Vector<Stack<Integer>>> chain = new Vector<>();
    Vector<Vector<Stack<Integer>>> cycle = new Vector<>();
    static int[] block = {0, 1, 1, 1, 0, 1, 2, 2, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 2, 0, 0, 0, 0, 0, 0};
    static Vector<Integer> temp = new Vector<>();// 申请的临时向量，存储一条链


    public static void main(String[] args) {
        new ModifiedAI();
    }


    /**
     * 无参构造方法
     */
    public ModifiedAI() {
        for (int index = 0; index < 3; index++) {
            move.addElement(new Vector<>());
        }
        for (int index = 0; index < 8; index++) {
            chain.addElement(new Vector<>());
        }
        for (int index = 0; index < 8; index++) {
            cycle.addElement(new Vector<>());
        }
        initMove0();
        updateCycle();
    }

    /**
     * 初始化move的第一个元素
     */
    public void initMove0() {
        for (int row = 0; row < ROWS; row++) {
            for (int col = 0; col < COLS - 1; col++) {
                move.elementAt(0).addElement(row * 1000 + col * 100 + row * 10 + col + 1);
            }
        }

        for (int col = 0; col < COLS; col++) {
            for (int row = 0; row < ROWS - 1; row++) {
                move.elementAt(0).addElement(row * 1000 + col * 100 + (row + 1) * 10 + col);
            }
        }
    }

    /**
     * <p>思路：
     * 1. 判断当前的格子属于哪种情况 四个角？ 四个边界？ 中间？
     * 2. 判断自由度是否为2并且没有遍历过
     * 是 --》 则按照对应的规则往下找下一个格子（用递归 准确的来说用回溯， 或者用动态规划（重复子问题太多，但是不独立））
     * 并把当前坐标的flag置为True， 并且把这个下标添加到vector里面
     * 否 ——》 则下标加一 </p>
     * <p>回溯缺点：
     * 会出现很多次重复计算 导致平均时间复杂度过大（  O（3.2^n） ）
     * 动态规划：
     * 子问题不独立，我不太会写</p>
     */
    public void updateCycle() {
        // 申请的临时数组 主要做判断是否已经遍历过了
        boolean[] isTraverse = new boolean[25];
        Vector<Vector<Integer>> cycle = new Vector<>();
        cycleDFS(0, isTraverse, cycle, false);

        for (int i = 0; i < cycle.size(); i++) {
            if (cycle.elementAt(i).size() == 8) {
                System.out.println(cycle.elementAt(i));
            }
        }
        System.out.println(cycle);
        // 判断cycle中的长度和类型，添加到对应的vector里
        // 添加到对应的数组...
        // ......
    }

    public void cycleDFS(int index, boolean[] isTraverse, Vector<Vector<Integer>> cycle, boolean isSimulateBegin) {
        if (DOFISTWO != block[index] && isSimulateBegin) {
            // 递归出口
            Vector<Integer> temp1 = new Vector<>(); // 临时申请一个vector用于拷贝数据
            for (int tempIndex = 0; tempIndex < temp.size(); tempIndex++) {
                temp1.addElement(temp.elementAt(tempIndex));
            }
            cycle.addElement(temp1);
            return;
        } else {
            if (!isTraverse[index] && DOFISTWO == block[index]) {
                // 没有遍历过
                isSimulateBegin = true; // 模拟开始的 标志置为true
                if (0 == index) {
                    //在左上角的情况
                    isTraverse[index] = true; // 模拟阶段
                    temp.addElement(-1);
                    cycleDFS(index + 1, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index + 5, isTraverse, cycle, isSimulateBegin);
                    isTraverse[index] = false;  // 回溯阶段
                    temp.removeElement(-1);

                } else if (4 == index) {
                    //在右上角的情况
                    isTraverse[index] = true; // 模拟阶段
                    temp.addElement(index);
                    cycleDFS(index + 5, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 1, isTraverse, cycle, isSimulateBegin);
                    isTraverse[index] = false;  // 回溯阶段
                    temp.removeElement(index);

                } else if (20 == index) {
                    //在左下角的情况
                    isTraverse[index] = true; // 模拟阶段
                    temp.addElement(index);
                    cycleDFS(index + 1, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 5, isTraverse, cycle, isSimulateBegin);
                    isTraverse[index] = false;  // 回溯阶段
                    temp.removeElement(index);

                } else if (24 == index) {
                    //在右下角的情况
                    isTraverse[index] = true; // 模拟阶段
                    temp.addElement(index);
                    cycleDFS(index - 1, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 5, isTraverse, cycle, isSimulateBegin);
                    isTraverse[index] = false;  // 回溯阶段
                    temp.removeElement(index);

                } else if (index >= 1 && index <= 3) {
                    // 在上边界的情况
                    isTraverse[index] = true; // 模拟阶段
                    temp.addElement(index);
                    cycleDFS(index + 1, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index + 5, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 1, isTraverse, cycle, isSimulateBegin);
                    isTraverse[index] = false;  // 回溯阶段
                    temp.removeElement(index);

                } else if (index >= 21 && index <= 23) {
                    // 在下边界的情况
                    isTraverse[index] = true; // 模拟阶段
                    temp.addElement(index);
                    cycleDFS(index + 1, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 1, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 5, isTraverse, cycle, isSimulateBegin);
                    isTraverse[index] = false;  // 回溯阶段
                    temp.removeElement(index);

                } else if (5 == index || 10 == index || 15 == index) {
                    // 在左边界的情况
                    isTraverse[index] = true; // 模拟阶段
                    temp.addElement(index);
                    cycleDFS(index + 1, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index + 5, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 5, isTraverse, cycle, isSimulateBegin);
                    isTraverse[index] = false;  // 回溯阶段
                    temp.removeElement(index);

                } else if (9 == index || 14 == index || 19 == index) {
                    // 在右边界的情况
                    isTraverse[index] = true; // 模拟阶段
                    temp.addElement(index);
                    cycleDFS(index + 5, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 1, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 5, isTraverse, cycle, isSimulateBegin);
                    isTraverse[index] = false;  // 回溯阶段
                    temp.removeElement(index);

                } else {
                    // 在中间的情况
                    isTraverse[index] = true; // 模拟阶段
                    temp.addElement(index);
                    cycleDFS(index + 1, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index + 5, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 1, isTraverse, cycle, isSimulateBegin);
                    cycleDFS(index - 5, isTraverse, cycle, isSimulateBegin);
                    isTraverse[index] = false;  // 回溯阶段
                    temp.removeElement(index);
                }

            } else {
                // 向下一个位置遍历
                if (24 == index) {
                    return;
                }
                cycleDFS(index + 1, isTraverse, cycle, false);
            }
        }
    }
}

